package com.zdp.leetcodeMiddle;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
* 题目描述：
* 输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 字符串的排列_38 {
    public static void main(String[] args) {
        字符串的排列_38 demo = new 字符串的排列_38();
        String[] abcs = demo.permutation3("aab");
        for(String temp : abcs){
            System.out.println(temp);
        }
    }

    /*
    * 解题思路：这不就是全排列那题嘛，利用回溯+深搜
    * 去重用 set
    * */
    public String[] permutation(String s) {
        Set<String> result = new HashSet<>();
        StringBuilder current  = new StringBuilder();
        int[] visited = new int[s.length()];
        f(current,s.toCharArray(),visited,0,result);
        return result.toArray(new String[]{});
    }

    public void f(StringBuilder cur,char[] s,int[] visited,int index,
                  Set<String> result){
        if(index == s.length){
            result.add(new String(cur));
        }
        // 排列，添加
        for(int i=0;i<s.length;i++){
            if(visited[i]==0){
                visited[i] = 1;
                cur.append(s[i]);
                f(cur,s,visited,index+1,result);
                // 回溯了
                visited[i] = 0;
                cur.deleteCharAt(cur.length()-1);
            }
        }
    }

    /*
    * 或者换个去重的思路，为什么会重复？
    * 因为字符串中有重复的字符出现
    * 换个思路： 每种字符在该位置只能出现一次，用一个Set来记录出现过的字符
    * */
    public String[] permutation2(String s) {
        List<String> result = new ArrayList<>();
        StringBuilder current  = new StringBuilder();
        int[] visited = new int[s.length()];
        f2(current,s.toCharArray(),visited,0,result);
        return result.toArray(new String[]{});
    }

    public void f2(StringBuilder cur,char[] s,int[] visited,int index
            ,List<String> result){
        if(index == s.length){
            result.add(new String(cur));
        }
        // 排列，添加
        // 利用 Set 来判断该位置出现的字符是否重复了
        Set<Character> temp = new HashSet<>();
        for(int i=0;i<s.length;i++){
                if(visited[i]==0){
                    if(!temp.contains(s[i])){
                        // 未出现过
                        temp.add(s[i]);
                        visited[i] = 1;
                        cur.append(s[i]);
                        f2(cur,s,visited,index+1,result);
                        // 回溯了
                        visited[i] = 0;
                        cur.deleteCharAt(cur.length()-1);
                    }
                }
        }
    }

    /*
    * 再或者，用交换的方法，就是设置一个指针，指针的左边区域为已排序，右边区域为未排序
    * 用这样的区域划分来代替 标记数组
    * */
    public String[] permutation3(String s) {
        char[] current = s.toCharArray();
        List<String> result = new ArrayList<>();
        f2(current,0,result);
        return result.toArray(new String[]{});
    }
    public void f2(char[] cur,int first,List<String> result){
        if(first == cur.length){
            result.add(new String(cur));
        }
        Set<Character> temp = new HashSet<>();
        for(int i=first;i<cur.length;i++){
            // 剪枝，判断是否重复
            if(temp.contains(cur[i])) {
                continue;
            }
            temp.add(cur[i]);
            // 0~first-1 区域是已经排列完毕的
            // 现在要对 first位置进行排列
            swap(cur,first,i);
            // 对 first+1位置进行排列
            f2(cur,first+1,result);
            // 回溯
            swap(cur,first,i);
        }
    }
    public void swap(char[] cur,int first,int second){
        char temp = cur[first];
        cur[first] = cur[second];
        cur[second] = temp;
    }
}
